home *** CD-ROM | disk | FTP | other *** search
/ ShareWare OnLine 2 / ShareWare OnLine Volume 2 (CMS Software)(1993).iso / infor / vrtexts.zip / GITR01.TXT < prev    next >
Text File  |  1993-04-17  |  30KB  |  589 lines
  1.  
  2.              The Mathematics of Three-Dimensional Manipulations
  3.                         and Transformations.
  4. ----------------------------------------------------------------------------
  5. Edition 1.2, by Trip V. Reece, June 1992.
  6. e-mail:  tvreece@caticsuf.csufresno.edu
  7. cis: Trip V. Reece    70620,2371
  8. Permission is given to copy and distribute without alteration.
  9.  
  10. Table of Contents
  11. -----------------
  12.  
  13. I.    Mapping 3d onto 2d
  14.       A. Skrinkage of X,Y dimensions
  15.       B. Vanishing Point
  16.      @ C. Aspect Ratio
  17.  
  18. II.   Translation and Scaling
  19.       A. The easy way
  20.       B. Via Matrices
  21.  
  22. III.  Rotation
  23.       A. Rotating a 2d coordinate
  24.       B. Rotation around another point
  25.       C. Rotating a 3d coordinate
  26.       D. The Matrix Solution
  27.  
  28. IV.   Matrices Unveiled
  29.       A. The Affine Transformation Generalized
  30.       B. Choices, Choices
  31.  
  32. V.   Z-Buffering
  33.      A. Why?
  34.      B. How?
  35.  
  36. VI.  Techniques
  37.      A. Bresenham's Drawing algorithm
  38.  
  39.  
  40.  
  41. I.  Mapping Three-Dimensional coordinates onto a Two-Dimensional Plane
  42.  
  43.      Although the title for this entry appears stultifying, indeed formidable,
  44. it is little other than identifying the relationships between distance and
  45. perspective.  The most important concept in 3d display is the apparent
  46. shrinkage of objects as they recede.  The other concept to keep in mind is
  47. the idea of a vanishing point.  It would be easier to simply transcribe the
  48. formula here, but to properly implement a 3-dimensional system, a thorough
  49. knowledge and understanding of EACH aspect of the system is VITAL.
  50. Otherwise, how can you track down slow operations and optimize efficiently?
  51.      The goal of this mapping function is to be able to pass it the
  52. three-dimensional coordinates and have it return the two dimensional
  53. coordinates for the monitor screen.  To understand how the mapping works, try
  54. to visualize a transparent, flat, rigid, plastic sheet with dots marked on it
  55. in a regular pattern, like so:
  56.    . . . . .
  57.    . . . . .
  58.    . . . . .
  59.    . . . . .
  60.  
  61.      Now, imagine each of these dots to be 3cm from the dot above/below or to
  62. the left or right of it.  Imagine now, if you will, another, perfectly
  63. identical sheet of plastic exactly 3cm from the first, parallel to the first
  64. and further away from you than the first.  Now, imagining how it would look,
  65. you would notice that the X and Y dimensions are contracted with greater
  66. intensity the further away a sheet of plastic is from you.  The marks on the
  67. plastic appear to be "pulled in" to the point directly in front of your
  68. eyeball, contracted >towards< that point.  The first concept, that of
  69. diminishing size with distance is given by the relationship:
  70.  
  71.    Size (= Original Size / Distance
  72.  
  73.      Note: The (= symbol is my ascii approximation for an alpha, the symbol
  74. for >proportional to<.  This, however, does not account for the vanishing
  75. point, the second concept used here.  To get another perspective on how the
  76. vanishing point works, find a flat floor with a regular pattern of parallel
  77. lines on it (they're easy to find) and stand vertical in front of it.  Now,
  78. using a single eye, look towards the horizon, and with two rulers, align
  79. their edges along with the parallel lines on the floor.  Hold the rulers in
  80. front of your face, also vertical, and each should point at a slightly
  81. different angle from the other.  Now, look at the rulers that you have lined
  82. up.  If you follow their edges to the point where they would have intersected
  83. if they were long enough, you (should)/will find that they meet at a point
  84. directly in front of your eye.  This point is called the vanishing point, and
  85. is used by artists to construct realistic perspective drawings.
  86.      Typically, to achieve a more realistic rendering, a cut-off distance is
  87. used to make points that are more than a certain distance away disappear.  To
  88. avoid the magnifying effect that would be evident when rendering an object
  89. that is of a distance less than one all objects closer than 1 unit of
  90. distance away are cut off.  The reason an object so close would become
  91. magnified is because the relationship  Size (= original_size / distance,
  92. would make 1/distance larger than 1, therefore multiplying the original size
  93. by a value greater than 1.
  94.      We can now reveal the first mapping function, which although incomplete,
  95. provides a clear understanding of its function.
  96.  
  97.                                                       ( Equation 1-1 )
  98.   Precondition:  Z is greater than or equal to 1.
  99.   Value: Shrinkage = ( 1 - scale / Z )
  100.   New X =  Old_X - Shrinkage * Old_X
  101.   New Y =  Old_Y - Shrinkage * Old_Y
  102.  
  103.      Now, we have declared Shrinkage to be the value of one minus the value
  104. of scale divided by the distance plus one.  Ignore scale for now, the value Z
  105. is the Z coordinate of the three-dimensional point.  If you multiplied out
  106. the expanded form of Shrinkage into the value of New X you would get:
  107.   New X =  Old_X - Old_X * ( 1 - scale/Z )
  108.   which is the same as:
  109.   New X = Old_X - Old_X + Old_X * scale / Z
  110.   which is the same as:
  111.   New X = Old_X / Z  * scale
  112.  
  113.      Why do we calculate the value of Shrinkage at all?  Because it is used
  114. in both the New X and New Y caluclations, and also because the picture this
  115. would produce does not look "right."  Let's first reason out the meaning of
  116. the "scale" value.  During practice, it looks really weird for an object to
  117. recede so far into the distance that it nearly touches the vanishing point.
  118. Let's simply say that scale's value is most apparent when it equals 1.  The
  119. theory doesn't yet explain why the value of scale is needed, so let's examin
  120. it a bit more carefully.
  121.      For a realistic image, the vanishing point is usually from one fourth
  122. the total height to one third of the total height down from the top of the
  123. image, and usually in the middle of the left/right length.  I can't explain
  124. why this looks "right," it may look completely wrong to some, but I've heard
  125. no complaints yet.  Now, to revise the formulas:
  126.  
  127.                                                       ( Equation 1-2 )
  128.    PreCondition:  Z is greater or equal to 1.
  129.    Shrinkage = ( 1 - scale / Z )
  130.    New X = Old_X - Shrinkage * Old_X
  131.    New Y = Old_Y - Shrinkage * ( Old_Y - EyeLevel )
  132.  
  133.      A few assumptions are made here, first: that the origin is located in
  134. the center of the screen, and that EyeLevel is a positive number.  EyeLevel
  135. tells us how HIGH UP from the origin the vanishing point should be.
  136. Typically, if the vertical resolution of the screen is MaxY then the maximum
  137. positive coordinate would be MaxY / 2 and if this value were divided by 3
  138. then you would have EyeLevel = MaxY / 6.  What the subtraction of MaxY does
  139. to the incoming Y coordinates is to translate everything UP.  Yes, it sounds
  140. backwards, but when you subtract inside the parantheses, it becomes addition
  141. outisde of the parantheses, so it really is ADDED, but added BEFORE it is
  142. mapped onto the 2-d plane.  Now, why isn't the X coordinate similarly
  143. translated?  Because: in a typical picture, the vanishing point is in the
  144. center of the horizontal direction, which is where the origin is in this
  145. implementation.  If the origin were anywhere else on the screen, it >would<
  146. have to be translated to the center of the screen.
  147.      This should now help to explain how the value of "scale" works.  In
  148. practice, a large value of scale tends to make the horizon much closer.  In
  149. fact, this is exactly what scale does for us.  It narrows the depth of field,
  150. in a sense.  If you increase the value of scale from 1 to a large value,
  151. objects that previously stretched back towards the vanishing point now seem
  152. to be much thinner, and hence more realistic.  The value of scale is
  153. dependant upon the horizontal resolution of the screen.  I have found that a
  154. setting scale equal to the horizontal resolution provides reliable results.
  155. Fiddle around with this value, but after a while, you will want the scale to
  156. remain constant in your program.
  157.      One other nagging little problem with all of this is the dreaded aspect
  158. ratio.  Depending on the graphics mode you are in, if the maximum X
  159. resolution is not the same as the maximum Y resolution then you must, that is
  160. >MUST< scale either the final X or final Y coordinate by this ratio.  You
  161. will want to compute this ratio at the beginning of your program so as to
  162. avoid any unnecessary divides.  This is how to do it:
  163.   Ratio = MaxYresolution / MaxXresolution
  164.   Now, this ratio is usually, 1.333333... for modes such as 640x480, or
  165. 800x600, or 1024x768, but may change as video displays improve and older
  166. modes, such as 320x200, are used.  To convert your "final" X and Y
  167. coordinates into something that you can plot on the monitor you must multiply
  168. the X coordinate by this ratio before you plot the point.  Alternatively, you
  169. can computer the reciprocal of the ratio, and multiply the "final" Y value by
  170. this "inverse ratio" to scale it that way.  But always remember to avoid
  171. division wherever possible, multiplication of non-integers is much faster
  172. than division by anything, especially zero.  :-)
  173.      That's it for mapping! Feel free to use equation 1-2 in any of your
  174. programs!
  175.  
  176.  
  177. II.  Translation and Scaling in Three Dimensions
  178.  
  179.      Starting with a definition: Translating a three-dimensional coordinate
  180. means to simply add a value to each of the X, Y, and Z coordinates.  Scaling
  181. a three-dimensional coordinate means to simply multiply each of the X, Y, and
  182. Z coordinates by a value.  This is irrelevant in dealing with single points,
  183. but when this is performed to a grouping of points, such as those in a cube,
  184. you can translate each coordinate by the same values for X Y and Z, to move
  185. the cube about in three dimensions.  Scaling the coordinates definitely
  186. provides for an interesting (i.e. entertaining) effect.  Objects will grow or
  187. shirnk depending on the value it is scaled by.  Scaling a single axis can
  188. elongate or shrink an object along that axis.
  189.      Typically, scaling occurs infrequently in a 3d modelling system, whereas
  190. translations are the basis of animation and interactive displays.  Note:
  191. Translation provides for movement in ONLY >along< the X, Y, and Z axes.
  192. Rotation is another matter entirely.
  193.  
  194.  
  195. III.  Rotation
  196.  
  197.      Since 3d geometry is really no different from 2d geometry, except with
  198. regards to the complexity of visualizing the math, rotations in 3d are
  199. similarly rooted in 2d geometry.  Warning: If you haven't had trigonometry
  200. experience, you will not understand this- read a book on it.
  201.      Now, everything in digital computers is usually expressed in integers or
  202. in rounded off floating-point numbers.  Coordinates of objects in either 2 or
  203. 3 dimensions is usually done in Cartesian, or Rectangular coordinates.  This
  204. means we have distinct values for X, Y (and/or Z) that are unique to that
  205. point.  In dealing with rectangular coordinates, when we want to rotate a
  206. point about the origin (0,0) in two-dimensions, we would convert the X,Y
  207. coordinate into an (R,Theta) polar coordinate, add the angle we wish to
  208. rotate the point to Theta, and then convert (R,New_Theta) back into
  209. rectangular.  This is honestly one of the quickest methods to rotate a single
  210. point about the origin.  The following identities are useful, indeed
  211. >necessary< to compute the rotated X and Y values.
  212.         ___________
  213.   R = \/ X^2 + Y^2
  214.   or:
  215.   R = ( X^2 + Y^2 ) ^ 0.5
  216.  
  217.   X = R * Cos (Theta)
  218.   Y = R * Sin (Theta)
  219.  
  220.   Tangent ( Y / X ) = Theta
  221.   Theta = ArcTangent ( Y / X )
  222.  
  223.   Sine ( Y / R ) = Theta
  224.   Theta = ArcSin ( Y / R )
  225.  
  226.   Cosine ( X / R ) = Theta
  227.   Theta = ArcCos ( X / R )
  228.  
  229.      The value of R remains constant during the rotation.  We first compute
  230. the value of R then.
  231.  
  232.   R = sqrt ( Old_X * Old_X + Old_Y * Old_Y )
  233.  
  234.      Now, we must compute the OLD value of theta.
  235.  
  236.   Theta = ArcTan ( Old_Y / Old_X )
  237.  
  238.      Now, we must compute the new values of X and Y.
  239.  
  240.   New_X = R * Cos ( Theta + RotateAngle )
  241.   New_Y = R * Sin ( Theta + RotateAngle )
  242.  
  243.      Ahh, but wait!  This will not work all the time!  Why not?  Because when
  244. Old_X is negative, the value of Theta will be the value of the reference
  245. angle, NOT the angle from the origin!  A simple fix is to use the following
  246. code instead:
  247.  
  248.   New_X = R * Cos ( Theta + RotateAngle )
  249.   If Old_X < 0 then New_X = New_X + Pi
  250.  
  251. -or- if you are working in degrees:
  252.  
  253.   If Old_X < 0 then New_X = New_X + 180
  254.  
  255.   and not forgetting to include:
  256.  
  257.   New_Y = R * Sin ( Theta + RotateAngle )
  258.  
  259.      The conversion between radians (it has pi in it) into degrees is to
  260. multiply the radian measure by ( 180 / Pi ) and to convert degrees into
  261. radians, you multiply the degree measue by ( Pi / 180 ).  What this means is
  262. that 2*Pi radians equals 360 degrees, 180 degrees equals Pi radians, and 0
  263. degrees equals 0 radians.  When you have a negative Old_X value, the value of
  264. Theta returned by ArcTangent ( Y / X ) is the angle measured from the left
  265. handed side of the x axis, this angle is the angle measured DOWN from the left
  266. side, not from the right side of the x axis.  Adding Pi radians (180 degrees)
  267. gives us the angle from the right side-- a positive value of Y will cause the
  268. ArcTangent function to return a negative angle.  This negative angle is the
  269. angle UP from the left side of the x axis; adding 180 degrees gives us the
  270. angle from the right side.  When X >and< Y are negative, the ArcTangent
  271. function gives us a positive angle, the angle DOWN from the left side of the
  272. x axis.  Adding 180 degrees clearly gives us the angle from the right side.
  273. Remember now, that angles are measured CounterClockwise from the right side
  274. of the x axis to the angle Theta.  If we did not know the original
  275. coordinates of X and Y, we would not be able to determine the correct value
  276. of Theta because the ArcTangent function only returns values between -90
  277. degrees and +90 degrees (or -Pi/2 radians to +Pi/2 radians.)
  278.      Suppose we didn't want to rotate the point about the origin, but about
  279. another point on the X,Y plane?  Simplicity itself!  Look at the rotation as
  280. a rotation about the origin, only the origin is displaced by the coordinates
  281. of the point about which you are really rotating (re-read that sentence if
  282. necessary.)  Call that second point the origin, and you're set.  If you make
  283. the point you want to rotate relative to the origin the same as it is
  284. relative to the second point, then translate it back, you've got it.  So, if
  285. we call the point about which we want to rotate Rot_X, Rot_Y then we are left
  286. with:
  287.  
  288.   Old_X2 = Old_X1 - Rot_X
  289.   Old_Y2 = Old_Y1 - Rot_Y
  290.  
  291.      Now, perform the rotation with Old_X2 and Old_Y2 in place of Old_X and
  292. Old_Y respectively.  Then, after you finish that, translate it back with:
  293.  
  294.   New_X2 = New_X1 + Rot_X
  295.   New_Y2 = New_Y1 + Rot_Y
  296.  
  297.      Now, if that isn't enough obfuscation, I shall write out the complete
  298. rotation with all variables in their proper place:
  299.  
  300.   R = (  (Old_X - Rot_X)^2 + (Old_Y - Rot_Y)^2 ) ^ 0.5
  301.   Theta = ArcTangent ( Y / X )
  302.   If (Old_X - Rot_X) < 0 then Theta = Theta + Pi
  303.   New_X = R * Cos (Theta + RotateAngle) + Rot_X
  304.   New_Y = R * Sin (Theta + RotateAngle) + Rot_Y
  305.  
  306.      To re-iterate this, RotateAngle is that angle in RADIANS
  307. COUNTERCLOCKWISE that you wish to rotate the original coordinate,
  308. (Old_X,Old_Y), about the point (Rot_X,Rot_Y).
  309.  
  310.      To implement this in a 3-dimensional frame, simply define what axis
  311. about which to wish to rotate a point (or group of points, as in an object)
  312. and in place of X and Y put the two axes that are left (NOT the axis about
  313. which you are rotating) in their place.  Now, the Rot_X and Rot_Y coordinates
  314. are the coordinates of the LINE that you are rotating the point(s) about.  If
  315. you wanted to rotate an object about the origin, leave Rot_x and Rot_Y zero.
  316. If you wish to rotate the object about it's center but along the Z axis,
  317. calculate the average of all X values and all Y values for that object and
  318. substitute those in for Rot_X and Rot_Y.  Remember that you can also rotate
  319. in the X or Y directions also!  If you wished to rotate an object about the X
  320. axis, around the origin for the X axis you would make Rot_X, Rot_Y equal to
  321. the Z and Y coordinates of the X axis: ZERO.  You would then put the Z and Y
  322. dimension coordinates in place of the values of Old_X and Old_Y (they're just
  323. variable identifiers, mathematically, you may rotate about any axis.)  If you
  324. mix up the order of Z and Y, (Frankly, I'm nt even sure about the "correct"
  325. order.) then the only side-effect will be that your rotations are reversed in
  326. direction.  It's all a matter of perspective, >you< decide what direction you
  327. wish to look head-on for each of the axes.  In my examples, I'm assuming the
  328. Z axis goes into the screen and X and Y are left/right and top/bottom
  329. respectively.
  330.  
  331. --Matrices
  332.      How is this solved with matrices?  It is not as easy to rotate about
  333. another point with matrices, but rotating about a single axis is relatively
  334. straightforward.  Consider the matrix*matrix problem below:
  335.  
  336. Rotation about X axis:
  337.  
  338.   |   1    0    0    0  |   | 1 |     |  A  |
  339.   |   0   cT   sT    0  | * | x |  =  |  B  |
  340.   |   0  -sT  -cT    0  |   | y |     |  C  |
  341.   |   0    0    0    1  |   | z |     |  D  |
  342.  
  343. [ cT = Cos(Theta), sT = Sin(Theta) ]
  344. If you go ahead with the matrix multiplication (I'll write it all out for
  345. those who are rusty this first time,)  then you get a result of:
  346.  
  347. A = 1*1 + 0*x + 0*y + 0*z = 1
  348. B = 0*1 + cos(Theta)*x + sin(Theta)*y + 0*z = x*cos(Theta) + y*sin(Theta)
  349. C = 0*1 + -sin(Theta)*x + -cos(Theta)*y + 0*z = x*-sin(Theta) - y*cos(Theta)
  350. D = 0*1 + 0*x + 0*y + 1*z = z
  351.  
  352. A = 1, B= x*cos(Theta)+y*sin(Theta), C= -x*sin(Theta)-y*cos(Theta), D= z
  353. New_X = B
  354. New_Y = C
  355. New_Z = D
  356.  
  357. This is the rotation of a point (x,y,z) about the X axis, for Theta degrees.
  358. I'd guess this is a correct rotation... But the value of C seems to be
  359. incorrect.  However, I will stick to non-matrix calculations to eliminate all
  360. those unnecessary ???*0 + ???*0 + ???*1 operations.  [ I consent that these
  361. transforms make no sense to me. ]
  362.  
  363.  
  364. Rotation about Y axis:
  365.  
  366.   |  cT    0  -sT    0  |   | 1 |     |  A  |
  367.   |   0    1    0    0  | * | x |  =  |  B  |
  368.   | -sT    0   cT    0  |   | y |     |  C  |
  369.   |   0    0    0    1  |   | z |     |  D  |
  370.  
  371. In this case:
  372.  
  373. A = 1*cos(Theta) + 0*x + y*-sin(Theta) + 0*z = cos(Theta) - y*sin(Theta)
  374. B = 0*1 + 1*x + 0*y + 0*z = x
  375. C = 1*-sin(Theta) + 0*x + y*cos(Theta) + 0*z = -sin(Theta) + y*cos(Theta)
  376. D = 0*1 + 0*x + 0*y + 1*z = z
  377.  
  378. Again, this really looks pretty wrong.  Perhaps I'm not multiplying matrices
  379. correctly, or maybe the matrices are set up wrongly.  However, if it works-
  380. use it.
  381.  
  382.  
  383. Rotation about Z axis:
  384.  
  385.   |  cT   sT    0    0  |   | 1 |     |  A  |
  386.   | -sT   cT    0    0  | * | x |  =  |  B  |
  387.   |   0    0    1    0  |   | y |     |  C  |
  388.   |   0    0    0    1  |   | z |     |  D  |
  389.  
  390. In this case:
  391.  
  392. A = 1*cos(Theta) + x*sin(Theta) + 0*y + 0*z = cos(Theta) + x*sin(Theta)
  393. B = -sin(Theta)*1 + x*cos(Theta) + 0*y + 0*z = -sin(Theta) + x*cos(Theta)
  394. C = 0*1 + 0*x + 1*y + 0*z = y
  395. D = 0*1 + 0*x + 0*y + 1*z = z
  396.  
  397. Now, this may make some sense.  Rotating about the z axis should only affect
  398. the x and y coordinates.  Hmm, in this case A and B >must< hold the new X and
  399. Y coordinates, since C contains an unchanged value of y.  Well, that's all
  400. about rotation with matrices that I'm prepared to be flamed for.
  401.  
  402. [ I honestly don't understand how this works, if it does at all. ]
  403.  
  404.  
  405. IV.  Matrices Unveiled
  406.  
  407. This section is postponed until I can get some accurate information about the
  408. matrices for rotation and other affine transformations.
  409.  
  410.  
  411. V.   Z-Buffering - The how's and the why's.
  412.  
  413.      Okay. translation and rotation may be all fine and dandy, but suppose I
  414. want to display my teapot that I've got encoded in a very nice compact data
  415. structure, but it looks transparent.  In fact, it looks like a wireframe,
  416. which it is!
  417.      -How to go about Z-Buffering-
  418.      First, get the memory.  Wherever possible, grab memory.  You will need
  419. for this exercise: enough memory for 3 times the video resolution in pixels,
  420. for example:  320x200 = 64000.  You will need 320x200x3 = 192000 bytes for
  421. this, unless you choose to perform some in-memory compression, an adivsable
  422. technique! This assumes you are using 8-bit color, i.e. 256 color.
  423.      First, reserve one byte for each pixel on the screen as part of a
  424. "virtual" screen.  This byte will store the color for that pixel once the 3d
  425. mapping and depth checking is complete.  Initialize this array with the
  426. background color of your choice.
  427.      Next, reserve two bytes (using the type integer, for example) for each
  428. pixel on the virtual screen in another array (yes this spans two segments of
  429. memory or more.)  These two bytes store the distance of the pixel in the
  430. range from 0 .. 65535.  This is the Z-Buffer itself.  In actuality, it
  431. shouldn't be called a Z buffer in a perspective rendering modeller.  It is
  432. properly a Distance-Buffer, but in an orthographic environment, the depth is
  433. the same as the Z coordinate, so the name stuck.  Oh well.  Initialize this
  434. array of distances with the value of 65535, or whatever your yon/hither
  435. values dictate.  It is a good idea to set a maximum distance on the objects
  436. you render, as well as a minimum distance- this prevents unnecessary
  437. calculations that would end up in an object rendered that only appeared as
  438. three small pixels not worthy of being called a polygon, or an impossibly
  439. huge triangle (for example) that covers up everything else on the screen.
  440. Use your judgement.
  441.      To draw a single frame now:  Scroll through your list of objects that
  442. are in visible sight.  Calculate the distance of each vertex from your
  443. eyeball using the pythagorean distance formula:
  444.  
  445.                ______________________
  446.   Distance = \/  X^2  +  Y^2  +  Z^2
  447.   or:
  448.   Distance =  ( X^2 + Y^2 + Z^2 ) ^ 0.5
  449.  
  450.      Now, calculate the coordinates of the mapped point on the 2d plane for
  451. this vertex.  (This should account for the vanishing point, as well as
  452. perspective.)  Now, compare the value of this distance with the value of the
  453. distance contained in the array of distances at the pixel location you just
  454. found the 2d mapped coordinates of.  If this vertex is of a less distance
  455. then replace the byte in the array of color with the color of this pixel, and
  456. store the calculated distance into the "Z-Buffer" array of distances at the
  457. location where you found it to lie on the 2d plane.  The gist of this all is
  458. to compare the distance of a point with the distance found in the array, if
  459. the distance already in the array is less than the distance of the pixel we
  460. are checking, then throw out that new pixel.  A pixel closer to you will
  461. "cover up" a pixel that is farther away.
  462.      To Z-Buffer a polygon, the vertices of the polygon must be projected
  463. onto the Z-Buffer plane, and checked for overlapping.  Even if the vertices
  464. aren't visible, there may be points on the polygon that >are< visible due to
  465. a "hole" in another polygon that just happens to be blocking the rest of the
  466. polygon we are rendering.  Instead of calculating the distance to each pixel
  467. of the polygon (entailing far too many squareds and square root operations to
  468. be feasible on most 80x86's) a form of interpolation may be used provided the
  469. four vertices and their distances; and upon the condition that the polygon is
  470. perfectly flat.  Of course Z-Buffering can also apply to non-polygonal
  471. shapes, however, it radically increases rendering time to use non-polygons.
  472.      After all the shapes/polygons have been rendered onto the virtual
  473. screen, the screen of visible colors must be copied into the video area.
  474. This can be quickened by storing the color array in video memory to begin
  475. with, and page in the new screens as they are available.  Be sure not to have
  476. the video screen showing that you are currently Z-Buffering!  That would give
  477. away the secret! :-)
  478.      Another improvement to make that is simplified when Z-Buffering is
  479. shading polygons.  Simply calculate the angle between the polygon normal (the
  480. perpendicular to the polygon's surface) and the light source (a "global"
  481. value) and take the cosine of this angle to get the intensity of the light
  482. reflected off the polygon.  Be sure to multiply the value of the cosine by
  483. the maximum allowable intensity, since cosine returns values ranging from
  484. -1,...+1.  Negative values either should be negated to get the positive
  485. value, or it could signify a hidden surface, i.e. a surface that faces away
  486. from the viewer.
  487.  
  488.  
  489. VI.  Techniques and Algorithms
  490.  
  491.      Bresenham's Line Drawing Algorithm
  492.         -The importance of this algorithm is evident when it is implemented
  493.          with ONLY integer math.  This can drastically improve calculation
  494.          times.
  495.  
  496.      This function takes in the X and Y coordinates of the endpoints of the
  497. line to be drawn.  To make it more versatille, it also will accept the color
  498. of the points it is to plot.
  499.  
  500.      The whole trick behind how this works is based on the mathematical fact
  501. that multiplication is really only repeated addition, and division is really
  502. only repeated subtraction.  There are two cases for the line drawing
  503. algorithm, 1: a line with a slope >= 1, and 2:  a line with a slope < 1.
  504. Since slope is  (delta Y)/(delta X) this means that the algorithm is
  505. dependent upon the fact that deltaY or delta X is the larger of the two.
  506. Let's consider case 2, where delta X exceeds delta Y.
  507.  
  508.      The algorithm "follows" along the X-axis, incrementing the x value of
  509.      the line it plots by one each time, and it calculates the value of y on
  510.      each run through the x increment loop.  A variable which could be called
  511.      "Cycle" is first initialized to the value of one half of delta X.  This
  512.      variable, Cycle will be incremented by the value of delta Y and then
  513.      checked against the value of delta X.  If cycle is greater than delta X
  514.      then the value of the y-coordinate to be plotted is upped by one
  515.      (assuming the line's slope is positive) and the value of Cycle has the
  516.      value of delta X subtracted from it.  The value of the x coordinate of
  517.      the point where the algorithm plots the new point each run through the
  518.      loop is incremented by one, unconditionally.  Now, another run through
  519.      the loop will give us:  increment Cycle by delta Y, check to see if it's
  520.      greater than delta X, (If YES: Cycle=cycle-delta X  and
  521.      Y_plot=Y_plot+1, else If NO: then don't change Y_plot.)  Now,
  522.      X_plot=X_plot+1.
  523.  
  524.      Perhaps an table of the values of Cycle, X_plot, & Y_plot as the loop is
  525. executed will better explain what is happening.  The values passed to the
  526. algorithm are called  x1, y1, x2, y2.
  527.  
  528. delta Y = y2 - y1 = 4     ( arbitrary points chosen for clarity )
  529. delta X = x2 - x1 = 9
  530.  
  531.   Cycle    |   X_Plot   |   Y_Plot
  532. -----------+------------+------------
  533.          4 |   x1       |    y1
  534.    4+4=  8 |   x1+1     |    y1
  535. 8+4=12-9=3 |   x1+2     |    y1+1          ( y1 is incremented because cycle
  536.    3+4=  7 |   x1+3     |    y1+1            overflowed delta X )
  537. 7+4=11-9=2 |   x1+4     |    y1+2          ( <-- overflowed again! )
  538.    2+4=  6 |   x1+5     |    y1+2
  539. 6+4=10-9=1 |   x1+6     |    y1+3          ( <-- another overflow )
  540.    1+4=  5 |   x1+7     |    y1+3
  541. 5+4=9-9= 0 |   x1+8     |    y1+4          ( cycle must never = delta x )
  542.    0+4=  4 |   x1+9     |    y1+4
  543.  
  544. Here the loop ends because delta X = 9 and x1+9 equals delta X.  Actually,
  545. this is leaving out an important detail:  if y2 is below y1 then instead of
  546. adding a positive 1 for each overflow of Cycle, a 1 must be subtracted.  This
  547. can be done easily by setting a variable called Increment equal to positive
  548. one or negative one at the beginning of the routine.
  549.  
  550. In the case of delta Y being larger than delta X, follow the same procedure
  551. as above, but the loop will follow the line vertically, so replace delta X
  552. with delta Y and vice versa.
  553.  
  554. It can be shown that the pattern that Cycle takes on needs not be calculated
  555. beyond a certain point.  As soon as Cycle regains the value it had to begin
  556. with (delta X divided by two, rounded down) it will follow the same pattern
  557. again and again.  I suspect that Cycle will always begin to repeat at or
  558. before delta_X number of positions down the list.  It is possible that the
  559. algorithm could beoptimized even further- calculate the first delta_X values
  560. for Cycle, perform a check and identify each position where cycle
  561. >>decreases<<  (i.e. it has overflowed and Y_Plot must be incremented)- place
  562. a one at each point where Y_Plot must be incremented, and then follow along
  563. >this< array and increment Y_Plot (or X_Plot as the case may be) where a one
  564. occurs.  And if you have the Megs and Megs of memory available, you could
  565. precalculate each of these arrays for every possible combination of delta Y
  566. and delta X... Maybe that's going a bit far now-  :-).
  567.  
  568. Why use the Bresenham line drawing algorithm?  It's blazingly fast.  Consider
  569. the work needed in dividing half a zillion line slope calculations, in
  570. real-time.  This routine only requires addition, subtraction, and a check.
  571. The intel processors have been optimized to all hell for wicked speed at
  572. addition/subtraction/comparisons, whereas division will ALWAYS be slow slow
  573. slow...
  574.  
  575. ... More algorithms to come! ...
  576.  
  577. Note:  I intend this article to be a growing text to help decipher the cryptic
  578.        world of 3d, as I learn more I will add to this list.  I also know that
  579.        I, like most people of the younger generation, am prone to errors.
  580.        Tell me about them! I want to learn more about this, can't find or
  581.        afford most of the books on this subject, so anything you can tell me
  582.        will be appreciated! and included if it makes any sort of sense!
  583.  
  584.  
  585. -Trip V. Reece
  586. Any comments, suggestions, errata reports please email me.
  587. e-mail:  tvreece@caticsuf.csufresno.edu
  588.  
  589. i